package cn.edu.neu.softlab.jason.offer.jianzhioffer.datastructure;

/**
 * 剑指offer-面试8
 * 旋转数组的最小数字
 * 把一个数组最开始的脱岗额元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个
 * 旋转，输出旋转数组的最小的元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，改数组的最小值为1.
 */
public class Mianshi8 {
    public static void main(String[] args) throws Exception {
        int[] array = {5, 5, 5, 1, 2, 3, 4};
        System.out.println(min(array, 0, array.length - 1));
        System.out.println(minOffer(array));
    }

    public static int min(int[] array, int start, int end) throws Exception {
        int mid = (start + end) / 2;
        if (array[start] < array[end]) {
            return array[start];
        }
        if (start == end) {
            return array[start];
        } else if (start == mid) {
            if (array[start] > array[end]) {
                return array[end];
            } else {
                return array[start];
            }
        } else {
            if (array[mid] >= array[start]) {
                return min(array, mid, end);
            } else {
                return min(array, start, mid);
            }
        }
    }

    public static int minOffer(int[] array) throws Exception {
        if (array == null || array.length <= 0) {
            throw new Exception("空数组异常");
        }
        int start = 0;
        int end = array.length - 1;
        // mid初始化为start是为了降低在数组为升序时的迭代次数，此时最小值为array[0]
        int mid = start;
        while (array[start] >= array[end]) {
            if (end - start <= 1) {
                return array[end];
            }
            mid = (start + end) / 2;
            // 如{1, 0, 1, 1, 1} 或者 {1, 1, 1, 0, 1}这种情况，我们无法确定最小值在左区间还是右区间
            // 只能进行顺序查找
            if (array[mid] == array[start] && array[mid] == array[end]) {
                minInOrder(array, start, end);
            }
            if (array[mid] >= array[start]) {
                start = mid;
            } else {
                end = mid;
            }
        }
        return array[start];
    }

    private static int minInOrder(int[] array, int start, int end) {
        int result = array[start];
        for (int i = start + 1; i <= end; i++) {
            if (array[i] < result) {
                result = array[i];
            }
        }
        return result;
    }
}
